#include <list>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    vector<string> ans;
    void dfs(TreeNode* node, list<int> his) {
        his.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr) {
            string o = "";
            list<int>::iterator it = his.begin();
            o += to_string(*it);
            it++;
            for (; it != his.end(); it++) {
                o += "->" + to_string(*it);
            }
            ans.push_back(o);
        } else {
            if (node->left != nullptr) {
                dfs(node->left, his);
            }
            if (node->right != nullptr) {
                dfs(node->right, his);
            }
        }
        his.pop_back();
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        dfs(root, {});
        return ans;
    }
};